/**
 * @a https://leetcode.cn/problems/combination-sum/
 */

#include "../common.h"
class Solution {
private:
    vector<vector<int>> ret;
    vector<int> state;
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        int start = 0;
        bk(target, start, candidates);
        return ret;
    }
    void bk(int target, int start, const vector<int>& choices){
        if(target == 0)
        {
            ret.push_back(state);
            return;   
        }
        for(int i = start; i < choices.size(); ++i){
            if(target - choices[i] < 0) break;

            state.push_back(choices[i]);
            bk(target - choices[i], i, choices);
            state.pop_back();
        }
    }
};